高考申論題
109年
[資訊處理] 資料結構
第 一 題
📖 題組：
二、優先佇列（Priority Queue）是依管理物件的優先權來考量，在此我們考慮管理物件的鍵值（Key）愈小其優先權愈高，兩個主要操作則分別為加入（Insert）與擷取最小者（Delete_Min）。
二、優先佇列（Priority Queue）是依管理物件的優先權來考量，在此我們考慮管理物件的鍵值（Key）愈小其優先權愈高，兩個主要操作則分別為加入（Insert）與擷取最小者（Delete_Min）。
請說明如何利用優先佇列對n個鍵值進行排序。（6分）
📝 此題為申論題
思路引導 VIP
這題是在考 Heap Sort / Priority Queue Sort 的基本精神。思考順序為：先把所有未排序資料「放進去（Insert）」，接著不斷把優先權最高（最小）的資料「拿出來（Delete_Min）」，拿出來的順序自然就是排序好的結果。
優先佇列排序法
💡 利用優先佇列「依權重輸出」之特性，達成資料之遞增排序。
🔗 優先佇列排序處理流程
- 1 Insert 寫入 — 將 n 個未排序鍵值逐一存入佇列中。
- 2 Delete_Min 擷取 — 執行 n 次操作，每次取出當前最小值。
- 3 有序產出 — 將取出元素依序存放，完成遞增排序。
↓
↓
🔄 延伸學習：延伸學習：若以二元堆積實作，總時間複雜度為 O(n log n)。
